MIME-Version: 1.0
Server: CERN/3.0
Date: Monday, 06-Jan-97 19:23:39 GMT
Content-Type: text/html
Content-Length: 2290
Last-Modified: Tuesday, 17-Dec-96 19:09:43 GMT

<title>CS388G: Algorithms: Techniques and Theory, Fall 1996</title>

<h2> CS388G: Algorithms: Techniques and Theory, Fall 1996</h2>

<p>
Instructor: <a href="welcome.html">Vijaya Ramachandran</a>

<p>
Unique Number: 47840 

<p>

<ul>
<li> <a href="f96_desc.ps">Course Description (Course Handout 1)</a> 

<p>

<li> <a href="f96_handout2.ps">Course Handout 2</a> 

<p>

<li> <a href="f96_hw1.ps">Home Work 1</a> 

<p>

<li> <a href="f96_hw2.ps">Home Work 2</a> 

<p>

<li> <a href="f96/hw3.ps">Home Work 3</a>

<p> 
 
<li> <a href="f96/hw4.ps">Home Work 4</a>

<p> 
  
<li> <a href="f96/hw5.ps">Home Work 5</a>

<p> 
  
<li> <a href="f96/hw6.ps">Home Work 6</a>

<p>

<li> <a href="f96/finalpage.ps">Final Exam Instructions</a>

</ul>

<p> 
.
<p>
  
<h3> FINAL EXAM UPDATES:</h3>

<p>

Here are my responses to all questions I have received so far.
(The questions posed are in quotes.)

<ul>
<p>

``Problem 1 a) the last sentence " ... takes more time on sigma' than on
sigma." What does the word "time" refer? Amortized time ot Total time or
others?''

<p>

<li>ANSWER: Total time.

<p>

``Problem 1 ) well-known faces: 
Any data structure for disjoint sets requires Big-Omega(ma(m,n)) time in
the worst case, but in our text book it is Big-O, not Big-Omega, is
there any difference?''

<p>

<li> ANSWER: I meant Big-Omega (see the first sentence of the second paragraph
of the Chapter notes on p. 461).

<p>

``Problem 4) the last sentence: "... no two vertices on the cycle contain
distinct labels from the same Li?" , so two vertices on the cycle can
contain same labels , right?''

<p>

<li> ANSWER: Right.

<p>

``I think the problem 3 in the final exam is a little unclear. 
Does f(X) denote the size of the largest true k x k submatrix or the 
size of the largest true l x m submatrix of X, where l does not have 
to equal to m?''

<p>

<li> ANSWER: A submatrix of X is "true" only if it is k x k for some
k and all of its k^2 entries are true. 

</ul>

<p>

.

<p>

<h3> Updated on Friday, December 6.</h3> 

<p>

<h3> New Update on Monday, December 9: </h3>

 I have received some questions on the final exam, but I will not be
posting either the questions or answers to the questions. If you
have sent me a question, please address it yourself using your
best judgment.


</dl>


